/*
 * @lc app=leetcode.cn id=449 lang=javascript
 *
 * [449] 序列化和反序列化二叉搜索树
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */

/**
 * Encodes a tree to a single string.
 *
 * @param {TreeNode} root
 * @return {string}
 */


// [8,3,10,2,4,9,11]
// 8(3(2,4),10(9,11))
var serialize = function(root) {
  if(!root) return '';
  let ret = '';
  ret += root.val;
  if(!root.left && !root.right) return ret;

  ret += `(`;
  ret += serialize(root.left);
  if(root.right) {
    ret += `,`;
    ret += serialize(root.right);
  }
  ret += `)`;
  return ret;
};

// 状态机模型
var deserialize = function(data) {
  console.log(data)
  let scode = 0, 
  ind = 0, 
  k = 0; // 记录是左还是右
  let stack = [];
  let node = null;
  let root = null;
  while(ind < data.length) {
    let val = data[ind];
    switch(scode) {
      case 0: 
        if(val >=0 && val <=9) {
          scode = 1; // 节点
        } else if(val ==='(') {
          scode = 2; // 左
        } else if(val ===',') {
          scode = 3; // 右
        } else if(val ===')') {
          scode = 4; // 结束
        }
        break;
      case 1: // 根节点
        let num = 0;

        // 此处不能使用val代替data[ind]
        while(data[ind] >=0 && data[ind] <=9){
          num = num * 10 + +data[ind];
          ind++;
        }

        node = new TreeNode(num);
        if(!root) root = node;
        if(k == 1) {
          stack[stack.length - 1].left = node;
        } else if(k ==2){ 
          stack[stack.length - 1].right = node;
        }

        scode = 0;
        break;
      case 2:
        stack.push(node);
        k = 1;
        ind++;
        scode = 0;
        break;
      case 3: 
        k = 2;
        ind += 1;
        scode = 0;
        break;
      case 4: 
        stack.pop();
        ind++;
        scode = 0;
        break;
    }
  }
  return root;
}
// @lc code=end

